//
// Created by chao.li on 2023/12/22.
//

#ifndef SOLUTIONS_SOLUTION037_H
#define SOLUTIONS_SOLUTION037_H

#include <vector>
#include <set>
#include "../common.hpp"

using namespace std;

class Solution {

    struct MaybeChars
    {
        int count = 9;
        unsigned data;
        MaybeChars(){
            data = 0x1ff;
        }

        void erase(char chr){
            unsigned test = 1 << (chr - '1');
            if(data & test){
                count --;
                data &= ~test;
            }
        }

        void insert(char chr){
            unsigned test = 1 << (chr - '1');
            if(!(data & test)){
                count ++;
                data &= test;
            }
        }

        void clear(){
            data = 0;
        }

        void getChars(vector<char>& chars)
        {
            chars.clear();
            for (int i = 0; i <9; ++i) {
                unsigned test = 1 << i;
                if(data & test){
                    chars.push_back('1' + i);
                }
            }
        }
    };

    vector<vector<MaybeChars>> maybeChars;
    int fillCount = 0;

    const int SudokuNum = 9;

    void clearMaybe(vector<vector<MaybeChars>>& maybe, int i, int j, char chr)
    {
        // 同格子删除 temp
        auto gi = i / 3 * 3;
        auto gj = j / 3 * 3;
        for (int m = gi; m < gi + 3; ++m) {
            for (int n = gj; n < gj + 3; ++n) {
                maybe[m][n].erase(chr);
            }
        }

        // 同行删除 temp
        for (int k = 0; k < SudokuNum; ++k) {
            // 同格子的已经删除过了
            if(k >= gj && k < gj + 3){
                continue;
            }
            maybe[i][k].erase(chr);
        }

        // 同列删除 temp
        for (int k = 0; k < SudokuNum; ++k) {
            // 同格子的已经删除过了
            if(k >= gi && k < gi + 3){
                continue;
            }
            maybe[k][j].erase(chr);
        }
    }

    void fillMaybeChars(const vector<vector<char>>& board)
    {
        maybeChars.resize(SudokuNum);
        for (int i = 0; i <SudokuNum; ++i) {
            maybeChars[i].resize(SudokuNum);
            for (int j = 0; j < SudokuNum; ++j) {
                for (char k = '1'; k < '1' + SudokuNum; ++k) {
                    maybeChars[i][j].insert(k);
                }
            }
        }

        for (int i = 0; i < SudokuNum; ++i) {
            for (int j = 0; j < SudokuNum; ++j) {
                if(board[i][j] != '.'){
                    maybeChars[i][j].clear();
                    clearMaybe(maybeChars, i, j, board[i][j]);
                } else{
                    ++fillCount;
                }
            }
        }
    }

    void selectNext(vector<vector<char>>& board, vector<vector<MaybeChars>>& maybe, int& ri, int& rj)
    {
        size_t minSize = 10;
        ri = rj = -1;
        for (int i = 0; i < SudokuNum; ++i) {
            for (int j = 0; j < SudokuNum; ++j) {
                if(board[i][j] != '.'){
                    continue;
                }
                auto size = maybe[i][j].count;
                if(size == 0){
                    continue;
                }
                if(size == 1)
                {
                    ri = i;
                    rj = j;
                    return;
                } else if(size < minSize){
                    minSize = size;
                    ri = i;
                    rj = j;
                }
            }
        }
    }
    void copyMaybeChars(vector<vector<MaybeChars>>& maybe)
    {
        maybe.resize(SudokuNum);
        for (int i = 0; i < SudokuNum; ++i) {
            maybe[i].resize(SudokuNum);
            for (int j = 0; j < SudokuNum; ++j) {
                maybe[i][j] = maybeChars[i][j];
            }
        }
    }

    void reverseMaybe(const vector<vector<MaybeChars>>& maybe)
    {
        for (int i = 0; i < SudokuNum; ++i) {
            for (int j = 0; j < SudokuNum; ++j) {
                maybeChars[i][j] = maybe[i][j];
            }
        }
    }

    bool sudokuRec(vector<vector<char>>& board){
        if(fillCount <= 0){
            return true;
        }
        int i = 0, j = 0;
        selectNext(board, maybeChars, i, j);

        if(i < 0 || j < 0 || maybeChars[i][j].count == 0)
        {
            //填错了
            return false;
        } else {

            vector<char> maybes;
            maybeChars[i][j].getChars(maybes);
            bool success = false;
            for (auto fillChar : maybes) {
                // 备份 maybeChars
                vector<vector<MaybeChars>> copy;
                copyMaybeChars(copy);

                // 填写
                board[i][j] = fillChar;
                fillCount--;
                clearMaybe(maybeChars, i, j, fillChar);

                // 检查冲突
                if(!sudokuRec(board)){
                    //恢复
                    board[i][j] = '.';
                    fillCount++;
                    reverseMaybe(copy);
                } else{
                    return true;
                }
            }
            //试过了所有候选，都失败了
            return false;
        }
    }

public:
    void solveSudoku(vector<vector<char>>& board) {
        fillMaybeChars(board);
        sudokuRec(board);
    }
};

void test()
{
    vector<vector<char>> board = {
            {'5','3','.','.','7','.','.','.','.'},
            {'6','.','.','1','9','5','.','.','.'},
            {'.','9','8','.','.','.','.','6','.'},
            {'8','.','.','.','6','.','.','.','3'},
            {'4','.','.','8','.','3','.','.','1'},
            {'7','.','.','.','2','.','.','.','6'},
            {'.','6','.','.','.','.','2','8','.'},
            {'.','.','.','4','1','9','.','.','5'},
            {'.','.','.','.','8','.','.','7','9'},
    };

//    vector<vector<char>> board = {
//            {'.', '.', '9', '7', '4', '8', '.', '.', '.'},
//            {'7', '.', '.', '.', '.', '.', '.', '.', '.'},
//            {'.', '2', '.', '1', '.', '9', '.', '.', '.'},
//            {'.', '.', '7', '.', '.', '.', '2', '4', '.'},
//            {'.', '6', '4', '.', '1', '.', '5', '9', '.'},
//            {'.', '9', '8', '.', '.', '.', '3', '.', '.'},
//            {'.', '.', '.', '8', '.', '3', '.', '2', '.'},
//            {'.', '.', '.', '.', '.', '.', '.', '.', '6'},
//            {'.', '.', '.', '2', '7', '5', '9', '.', '.'}
//    };

    StopWatch clock;

    for (int i = 0; i < 1000; ++i) {
        Solution s;
        s.solveSudoku(board);
    }

    clock.stop("time");
    printvv(board);
}








#endif //SOLUTIONS_SOLUTION037_H
